# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/24 19:11
@FileName      : 普里姆(Prim)算法.py
@LastEditors   : None
@Editors       : PyCharm
"""

V = 6  # 图中点的个数
cost = [[0] * V for i in range(V)]
cost_dict = {"0-1": 7, "1-3": 3, "0-3": 8, "1-2": 6, "3-2": 4, "3-4": 3, "2-4": 2, "2-5": 5, "4-5": 2}
point_list = ['S', 'A', 'B', 'C', 'D', 'T']
for key in cost_dict:
    value = cost_dict[key]
    p1, p2 = [int(s) for s in key.split('-')]
    cost[p1][p2] = value
    cost[p2][p1] = value


def find_MST(cost):
    visited = [0] + [1] * (len(cost) - 1)
    tree = [0] * (len(cost) - 1)
    for i in range(len(cost) - 1):
        path = []
        weight = float('inf')
        for p1 in range(len(visited)):
            if visited[p1] == 1:
                continue
            for p2 in range(len(visited)):
                if visited[p2] == 0:
                    continue
                value = cost[p1][p2]
                if value > 0 and value < weight:
                    path = [p1, p2]
                    weight = value
        visited[path[1]] = 0
        tree[i] = path
    return tree


MinTree = find_MST(cost)
weight = 0
print("最小生成树:")
for p1, p2 in MinTree:
    value = cost[p1][p2]
    print(point_list[p1], '-', point_list[p2], 'weight:%d' % value)
    weight += value
print("总权值:", weight)
